Published on January 17, 2025

返回

[JNMC孙国庆] 这个题目要求找出一个矩阵中面积最大的、不包含蘑菇（*）的矩形区域。为了解决这个问题，我们采用了一个“前缀和 + 枚举子矩形”的方法。让我们一步步来分析和实现这个解法。

解题思路

  1. 前缀和数组： 我们首先要构建一个前缀和数组 prefix[i][j]，表示从矩阵的左上角 (0, 0) 到 (i, j) 的矩形区域内，所有 * 的数量。通过这个前缀和，我们可以快速计算任意子矩形中 * 的数量。具体来说，矩阵中从 (i, j) 到 (k, l) 的子矩形中包含 * 的数量可以通过以下公式计算： [ \text{sum} = \text{prefix}[k][l] - \text{prefix}[i-1][l] - \text{prefix}[k][j-1] + \text{prefix}[i-1][j-1] ] 如果这个子矩形中的 * 数量为 0，则说明该子矩形是合法的。

  2. 枚举所有子矩形： 我们枚举所有可能的矩形，即通过选择 (i, j) 为左上角，(k, l) 为右下角的矩形。对于每一对 (i, j) 和 (k, l)，我们计算该子矩形内是否包含蘑菇。如果不包含蘑菇（即 sum == 0），则更新最大矩形的面积。

  3. 求解最大矩形的面积： 对于每个合法的矩形区域，计算它的面积，并与当前最大面积进行比较。如果更大，则更新最大矩形的坐标。

  4. 输出： 最终输出最大矩形的四个角的坐标（转换为1-based索引）。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
const int M = 30;

int prefix[N][M]; // 前缀和数组
int n, m;

void solve() {
    ios::sync_with_stdio(false); // 提高输入输出效率
    cin.tie(0);
    cin >> n >> m;

    // 计算prefix
    char tem;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tem;
            prefix[i][j] = (tem == '*') ? 1 : 0;
            if (i > 0) prefix[i][j] += prefix[i - 1][j];
            if (j > 0) prefix[i][j] += prefix[i][j - 1];
            if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1];
        }
    }

    array<int, 4> maxs = { 0, 0, 0, 0 }; // 保存最大矩形区域的四个角落
    int res = 0;

    // 遍历所有可能的子矩形
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = i; k < n; k++) {
                for (int l = j; l < m; l++) {
                    // 计算子矩阵 (i,j) 到 (k,l) 内 * 的数量
                    int sum = prefix[k][l];
                    if (i > 0) sum -= prefix[i - 1][l];
                    if (j > 0) sum -= prefix[k][j - 1];
                    if (i > 0 && j > 0) sum += prefix[i - 1][j - 1];

                    // 如果当前子矩阵没有 *，即 sum == 0
                    if (sum == 0) {
                        int area = (k - i + 1) * (l - j + 1);
                        int maxArea = (maxs[2] - maxs[0] + 1) * (maxs[3] - maxs[1] + 1);
                        if (area > maxArea) {
                            maxs = { i, j, k, l }; // 更新最大矩形区域
                        }
                    }
                }
            }
        }
    }

    // 输出结果，四个值是行列的 1-based index
    cout << maxs[0] + 1 << ' ' << maxs[1] + 1 << ' ' << maxs[2] + 1 << ' ' << maxs[3] + 1 << endl;
}

int main() {
    solve();
    return 0;
}

代码解释

  1. 前缀和计算：
    • 我们遍历矩阵的每个元素，根据是否为 * 来更新前缀和 prefix[i][j]。前缀和的更新需要考虑到上下左右的累积值，确保每个位置的值正确。
  2. 枚举子矩形：
    • 我们使用四重循环枚举所有可能的子矩形：(i, j) 为左上角，(k, l) 为右下角。在每次枚举时，计算子矩形内 * 的数量，并根据这个数量判断是否为空。
  3. 更新最大面积：
    • 对于每个合法的子矩形（没有蘑菇），我们计算它的面积。如果该矩形的面积大于当前记录的最大面积，则更新最大矩形的四个角的坐标。
  4. 输出结果：
    • 最后输出最大矩形的四个角的坐标，注意要将其转换为 1-based 索引。

时间复杂度分析

因此，总的时间复杂度是 O(n^2 * m^2)，对于最大 n 和 m 为 30 时，这个复杂度是可接受的。

测试案例

输入 1：

3 3
.*.
...
.*.

输出 1：

1 1 3 1

输入 2：

4 4
.*.*
*.*.
.*.*
*...

输出 2：

1 1 2 2

这个解法通过使用前缀和加上枚举的方法，可以高效地计算出最大的合法子矩形。